On Newton-Raphson iteration for multiplicative inverses modulo prime powers

摘要

We study algorithms for the fast computation of modular inverses.Newton-Raphson iteration over $p$-adic numbers gives a recurrence relationcomputing modular inverse modulo $p^m$, that is logarithmic in $m$. We solvethe recurrence to obtain an explicit formula for the inverse. Then we studydifferent implementation variants of this iteration and show that our explicitformula is interesting for small exponent values but slower or large exponent,say of more than $700$ bits. Overall we thus propose a hybrid combination ofour explicit formula and the best asymptotic variants. This hybrid combinationyields then a constant factor improvement, also for large exponents.